In a data processing system, shared buses are used to interconnect plural resources together. For example, a data bus could be shared by various local area networks (LANs). The LANs transfer data between each other over the shared data bus.
Because of the potential of congestion that could arise with many resources using a single bus, some mechanism must be provided to control the trafficking of data over the bus. An arbiter prevents more than one resource from transmitting data on the bus at the same time. The arbiter also determines which particular resource gains access to the bus, typically on the basis of some priority scheme or protocol.
As discussed in Guibaly "Design and Analysis of Arbitration Protocols", IEEE Transactions on Computers, volume 38, number 2, February 1989, pages 161-171, the selection of an arbitration scheme is generally a choice between priority and fairness. In a priority based scheme, each resource has an assigned priority which determines the winning resource if two or more resources are competing for the bus. Fairness ensures that resources with the low priority will gain access to the bus without being completely locked out as could occur with heavy traffic over the bus.
Two fair arbitration protocols are round robin (or rotating) and first-come first-serve. Under a round robin arbitration scheme, the arbiter sequentially grants each resource access to the bus. No resource receives a second grant to the bus until all other resources have been given an opportunity to use the bus. Under a first-come first-serve arbitration scheme, resources are granted access to the bus in the order in which they requested it. Both of these schemes are very fair because each resource has a chance to access the bus. However, these schemes do not in general produce the best performance. Mean waiting time for the bus can be longer than is necessary. These schemes also cannot guarantee that certain critical resources will not wait longer than is allowable, with a resultant loss of data.
When priorities are assigned, access to the bus is granted among requesting resources according to their relative priority. No resource of a given priority may be serviced until all resources of a higher priority waiting for the bus have been served. Upon entering the queue for bus service, a resource is placed ahead of all resources with a priority lower than its own, and behind all resources with a priority higher than its own. Resources having equal priority may be served according to a first-come first-serve, round robin or some other priority scheme. If the arbitration scheme is non-preemptive, a resource first entering the queue will never interrupt the servicing of the resource that is using the bus, even if that resource has a lower priority. Under a preemptive scheme, the resource using the bus would be interrupted if a higher priority resource entered the queue.
Use of priorities can reduce system mean response times. Their use can also guarantee that those resources that cannot wait too long for servicing will receive it in a timely manner. Their use does introduce one drawback however. Low priority resources can be "shut out" from using the bus for unacceptably long periods of time.
Priority mechanisms are particularly important in systems used to transport isochronous data where guaranteed data bandwidth and low queuing delay are essential. Isochronous data, which may include voice, video, or other multimedia information, must be transported by the bus or other interconnection mechanism within fixed time constraints. An arbitration mechanism that provides an efficient means of allocating bus access is an essential part of isochronous and multimedia capable systems.